/*
 * @lc app=leetcode.cn id=22 lang=golang
 *
 * [22] 括号生成
 */

// @lc code=start
func generateParenthesis(n int) []string {
	cur := []byte{}
	ans := []string{}
	var dfs func(left, right int)
	dfs = func(left, right int) {
        if left > right {
            return
        }
		if len(cur) == n*2 {
			ans = append(ans, string(append([]byte{}, cur...)))
			return

		}
		if left > 0 {
			cur = append(cur, '(')
			dfs(left-1, right)
			cur = cur[:len(cur)-1]
		}

		if right > 0 {
			cur = append(cur, ')')
			dfs(left, right-1)
			cur = cur[:len(cur)-1]
		}
	}
	dfs(n, n)
	return ans
}

// @lc code=end

